Problème de Flavius Josèphe

Des soldats juifs, cernés par des soldats romains, sont obligés de former un cercle. Un premier soldat est choisi au hasard et est exécuté, le troisième à sa gauche est ensuite exécuté. Tant qu'il y a des soldats, la sélection continue. Le but est de trouver à quel endroit doit se tenir un soldat pour être le dernier et donc être épargné. Avec un nombre n de soldat formant le cercle et la position p du premier soldat tué le code doit renvoyer la position du dernier soldat en vie qui est epargné.
Chaîne à afficher si l'image ne peut s'afficher
Schéma du problème

Résolution du problème

Pour résoudre ce problème j'ai utilisée une liste chainée car cela permet de bien structurer le cercle. J'ai donc utilisé la classe que nous avions codée auparavant. J'ai realisé le code que les soldats regardent vers l'exterieur du cercle Je voulais faire une liste chainée circulaire afin que le dernier maillon soit en lien avec le premier. Mais c'était plus facile de changer la manière dont la position p évolue. Je crée donc une liste chainéé normale du nombre n de soldats. J'élimine le premier soldat se trouvant à la position p,et je diminue le nombre n qui est la taille de la liste. Je commence une boucle while qui est efféctuée tant que la liste a plus d'un élément. Je diminue de 3 la valeur p, si elle est négative je calcule la position pour parcourir le cerlce dans le 'bon sens'. Je supprime dans tout les cas le soldat à la postion p et décrémente la taille n du cercle. La position p parcourt donc le cercle a l'envers jusqu'à ce qu'elle ait finie un tour du cercle (soit que p devienne négatif), à ce moment elle le parcourt une fois dans le 'bon sens'.


Chaîne à afficher si l'image ne peut s'afficher
Liste chainée circulaire

Code


from Classe_pour_Listes import *
	
def flavius (n,p) :
    p-=1 #les indices sont zéro-indexés
    cercle=Liste()
    for i in range(1,n+1) : #on crée la liste chainée
        cercle.append(i)
    print(cercle)
    cercle.pop(p) #on élimine le premier soldat
    n-=1 
    while n>1:
        p-=3
        if p<0 : #si p est négatif on calcule la position du prochain soldat
            p=n+p
        cercle.pop(p) 
        n-=1 # on réduit la taille de la liste
        print(cercle)

    return cercle

print(flavius(7,1))
print(flavius(8,1))